OI代码模板计划 - 动态树 - LCT

代码：洛谷P3690 Link Cut Tree （动态树）

给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

#include <cstdio>
#include <iostream>
const int maxm = 1e7 + 10;
static int n, m, val[maxm];
inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int _read()
{
    register char ch = nc();
	register int sum = 0;
    while (ch < '0' || ch > '9') ch = nc();
    while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = nc();
    return sum;
}
static char pbuf[100000], *pp = pbuf;
inline void push(const char c)
{
    if (pp - pbuf==100000) fwrite(pbuf, 1, 100000, stdout), pp = pbuf;
    *pp++ = c;
}
inline void write(int x)
{
    static int sta[35];
    register int top = 0;
    do {sta[top++] = x % 10, x /= 10;} while(x);
    while (top) push(sta[--top] + '0');
}
namespace LCT
{
	static int top, son[maxm][2], fa[maxm], xr[maxm], stk[maxm], rev[maxm];
	inline void pushup(const int &x) { xr[x] = xr[son[x][1]] ^ xr[son[x][0]] ^ val[x]; }
	inline void pushdown(const int& x)
	{
		if (rev[x])
		{
			rev[son[x][1]] ^= 1, rev[son[x][0]] ^= 1, rev[x] = 0;
			std::swap(son[x][1], son[x][0]);
		}
	}
	inline bool isroot(const int& x) { return (son[fa[x]][1] != x && son[fa[x]][0] != x); }
	inline void rotate(const int& x)
	{
		register int fa1 = fa[x], fa2 = fa[fa1], l;
		if (son[fa1][0] == x) l = 0;
		else l = 1;
		register int r = l ^ 1;
		if (!isroot(fa1))
			(son[fa2][0] == fa1) ? (son[fa2][0] = x) : (son[fa2][1] = x);
		fa[x] = fa2, fa[fa1] = x, fa[son[x][r]] = fa1,
		son[fa1][l] = son[x][r], son[x][r] = fa1,
		pushup(fa1), pushup(x);
	}
	inline void splay(const int& x)
	{
		top = 1, stk[top] = x;
		for (register int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];
		for (register int i = top; i; i--) pushdown(stk[i]);
		while (!isroot(x))
		{
			register int y = fa[x], z = fa[y];
			if (!isroot(y))
			{
				if ((son[y][0] == x) ^ (son[z][0] == y)) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
	}
	inline void access(int x) { for (register int t = 0; x; t = x, x = fa[x]) splay(x), son[x][1] = t, pushup(x); }
	inline void makeroot(const int &x) { access(x), splay(x), rev[x] ^= 1; }
	inline int findroot(int x) { access(x), splay(x); while (son[x][0])x = son[x][0]; return x; }
	inline void split(const int &x, const int &y) { makeroot(x), access(y), splay(y); }
	inline void cut(const int &x, const int &y) { split(x, y); if (son[y][0] == x) son[y][0] = 0, fa[x] = 0; }
	inline void link(const int &x, const int &y) { makeroot(x), fa[x] = y; }
};
int main()
{
	n = _read(), m = _read();
	for (register int i = 1; i <= n; i++) val[i] = _read(), LCT::xr[i] = val[i];
	for (register int i = 1, opt, x, y; i <= m; i++)
	{
		opt = _read(), x = _read(), y = _read(); 
		if (!opt)
		{
			LCT::split(x, y),
			write(LCT::xr[y]), push('\n');
		}
		if (opt == 1)
			LCT::link(x, y);
		if (opt == 2)
			LCT::cut(x, y);
		if (opt == 3)
			LCT::access(x), LCT::splay(x), val[x] = y, LCT::pushup(x);
	}
	fwrite(pbuf, 1, pp - pbuf, stdout);
	return 0;
}

我竭尽全力卡常了…相信我…我已经无能为力了…

438ms。。。太惨了太惨了